#include <iostream>

using std::cout;
using std::endl;

struct Node{
    int data;
    Node *next = nullptr;

    Node(int dt):data(dt){}
    Node(){}
};

class List{
public:
    List()
    {
        head_ = new Node();
    }  

    ~List()
    {
        while(head_){
            Node *tmp = head_->next;
            delete head_;
            head_ = tmp;
        }
    }

public:
    Node *head_;
};

void foreach(List *list)
{
    Node *p = list->head_->next;
    while(p){
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

// 链表逆序
void reverse(List *list)
{
    Node *p = list->head_->next;
    list->head_->next = nullptr;
    while(p){
        Node *q = p->next;
        Node *tmp = list->head_->next;
        list->head_->next = p;
        p->next = tmp;

        p = q;
    }

    foreach(list);

}

void merge(List *list1, List *list2)
{
    /*
    定义一个结果链表，然后取出两个链表中较小的一个节点连接到结果节点，然后重复步骤，知道其中一个链表为空
    最后将不为空的链表连接到结果指针的最后，因为当前剩下的元素都是大于结果链表的元素 
    */ 
    List *ret = new List();  
    Node *retNode = ret->head_;
    Node *link1 = list1->head_->next;
    Node *link2 = list2->head_->next;
    while(link2 && link2){
        if(link1->data <= link2->data){
            retNode->next = link1;        
            link1 = link1->next;
        }else{
            retNode->next = link2;
            link2 = link2->next;
        }

        retNode = retNode->next;
    }

    if(link1){
        retNode->next = link1;
    }else{
        retNode->next = link2;
    }

}

void test()
{
    List *list = new List();
    Node *n1 = new Node(1);
    Node *n2 = new Node(2);
    Node *n3 = new Node(3);
    Node *n4 = new Node(9);

    list->head_->next = n1;
    n1->next = n2;
    n2->next = n3;
    n3->next = n4;


    foreach(list);

    List *list2 = new List();
    Node *nn1 = new Node(0);
    Node *nn2 = new Node(3);
    Node *nn3 = new Node(4);
    Node *nn4 = new Node(6);

    list2->head_->next = nn1;
    nn1->next = nn2;
    nn2->next = nn3;
    nn3->next = nn4;


    foreach(list2);


    merge(list, list2);
}

int main(int args, char *argv[])
{
    test();
    return 0;
}